class Solution {
public:
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    typedef pair<int, int> value;
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
    {
        int sign = image[sr][sc];
        if (image[sr][sc] == color) return image;
        priority_queue<value, vector<value>> q;
        q.push({ sr, sc });
        int sizer = image.size();
        int sizec = image[0].size();
        while (!q.empty())
        {

            auto [x, y] = q.top();
            image[x][y] = color;
            q.pop();

            for (int i = 0; i < 4; i++)
            {
                int row = x + dx[i];
                int col = y + dy[i];
                if (row < sizer && col < sizec && row >= 0 && col >= 0 && image[row][col] == sign)
                {
                    q.push({ row, col });
                }
            }
        }
        return image;
    }
};
class Solution {
public:
    int row, col;
    int numIslands(vector<vector<char>>& grid) {
        row = grid.size();
        col = grid[0].size();
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (grid[i][j] == '1')
                {
                    ret++;
                    fight(grid, i, j);
                }
            }
        }
        return ret;
    }
    int ret = 0;
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    typedef pair<int, int> value;
    void fight(vector<vector<char>>& grid, int _row, int _col)
    {
        queue<value> q;
        q.push({ _row, _col });
        grid[_row][_col] = '0';
        while (!q.empty())
        {
            auto [x, y] = q.front();
            grid[x][y] = '0';
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int i = x + dx[k];
                int j = y + dy[k];
                if (i >= 0 && i < row && j >= 0 && j < col && grid[i][j] == '1')
                {
                    grid[i][j] = '0';
                    q.push({ i, j });
                }
            }
        }
    }
};